package com.lihepeng.leecode.tree;

import org.apache.commons.lang3.StringUtils;

/**
 * 前缀树
 * 实现前缀搜索的功能
 */
public class TrieMap<V> {
    // ASCII 码个数
    private static final int R = 256;
    // 当前存在 Map 中的键值对个数
    private int size = 0;
    // 头部节点
    private TrieNode<V> root = null;
    public int getSize(){
        return this.size;
    }
    public TrieNode getNode(TrieNode<V> trieNode,String key) {
        TrieNode p =  trieNode;

        for (int i=0;i<key.length();i++) {
            if (p ==null) {
                return null;
            }
            char c = key.charAt(i);
            p = p.children[c];
        }
        return p;
    }
    public V getKey(String key) {
        if (StringUtils.isBlank(key)) {
            return null;
        }
        TrieNode<V> node = getNode(root, key);
        if (node ==null || node.val ==null) {
            return null;
        }
        return node.val;
    }
    public boolean containKey(String key){
        V val = getKey(key);
        return val !=null;
    }

    private static class TrieNode<V>{
        V val = null;
        TrieNode[]children = new TrieNode[256];

        public TrieNode(V val) {
            this.val = val;
            this.children = new TrieNode[R];

        }
    }
}
